package com.data.construct.array;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * 动态数组代码实现
 * 自己实现的ArrayList集合类
 *
 * @author sunhl
 * @Description:
 * @Date: created in 2024/10/15 0015 9:40
 * @Modified By:
 */
public class MyArrayList<E> {

    /**
     * 测试用例
     * @param args
     */
    public static void main(String[] args) {
        // 初始容量设置为 3
        MyArrayList<Integer> arr = new MyArrayList<>(3);

        // 添加 5 个元素
        for (int i = 1; i <= 5; i++) {
            arr.addLast(i);
        }

        arr.remove(3);
        arr.add(1, 9);
        arr.addFirst(100);
        int val = arr.removeLast();

        for (int i = 0; i < arr.size(); i++) {
            System.out.println(arr.get(i));
        }
    }


    private E[] data;

    private int elementSize;

    private static final int INIT_CAP = 10;

    public MyArrayList() {
        this(INIT_CAP);
    }

    public MyArrayList(int capacity) {
        data = (E[]) new Object[capacity];
        elementSize = 0;
    }

    /**
     * 增(尾部)
     *
     * @param e
     */
    public void addLast(E e) {
        int cap = data.length;
        // 看 data 数组容量够不够
        if (elementSize == cap) {
            resize(2 * cap);
        }
        // 在尾部插入元素
        data[elementSize] = e;
        elementSize++;
    }

    /**
     * 增(指定索引)
     *
     * @param e
     */
    public void add(int index, E e) {
        // 检查索引越界
        checkPositionIndex(index);

        int cap = data.length;
        // 看 data 数组容量够不够
        if (elementSize == cap) {
            resize(2 * cap);
        }

        // 搬移数据 data[index..] -> data[index+1..]
        // 给新元素腾出位置
        for (int i = elementSize - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        // 插入新元素
        data[index] = e;

        elementSize++;
    }

    /**
     * 增(首部)
     *
     * @param e
     */
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     * 删(首部)
     */
    public E removeLast() {
        if (elementSize == 0) {
            throw new NoSuchElementException();
        }

        int cap = data.length;
        // 可以缩容，节约空间
        if (elementSize == cap / 4) {
            resize(cap / 2);
        }

        E deleteElement = data[elementSize - 1];

        // 删除最后一个元素
        // 必须给最后一个元素置为 null，否则会内存泄漏
        data[elementSize - 1] = null;
        elementSize--;

        return deleteElement;
    }

    /**
     * 删(指定索引)
     *
     * @param index
     */
    public E remove(int index) {
        checkElementIndex(index);

        int cap = data.length;
        // 可以缩容，节约空间
        if (elementSize == cap / 4) {
            resize(cap / 2);
        }

        E deleteElement = data[index];

        // 搬移数据 data[index+1..] -> data[index..]
        for (int i = index + 1; i < elementSize; i++) {
            data[i - 1] = data[i];
        }

        data[elementSize - 1] = null;
        elementSize--;

        return deleteElement;
    }

    /**
     * 删(首部)
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 查
     *
     * @param index
     * @return
     */
    public E get(int index) {
        // 检查索引越界
        checkElementIndex(index);

        return data[index];
    }

    /**
     * 改
     *
     * @param index
     * @param element
     * @return
     */
    public E set(int index, E element) {
        // 检查索引越界
        checkElementIndex(index);
        // 修改数据
        E oldVal = data[index];
        data[index] = element;
        return oldVal;
    }


    ///////////////////////////////////////////// 工具方法  //////////////////////////////////////////////

    /**
     * 返回元素数量
     *
     * @return
     */
    public int size() {
        return elementSize;
    }

    /**
     * 判断是否无元素
     *
     * @return
     */
    public boolean isEmpty() {
        return elementSize == 0;
    }

    /**
     * 将 data 的容量改为 newCap
     * 缩容/扩容的基础方法, 实现一个简单的扩缩容的策略：
     * 当数组元素个数达到底层静态数组的容量上限时，扩容为原来的 2 倍；
     * 当数组元素个数缩减到底层静态数组的容量的 1/4 时，缩容为原来的 1/2。
     *
     * @param newCap
     */
    private void resize(int newCap) {
        E[] temp = (E[]) new Object[newCap];

        for (int i = 0; i < elementSize; i++) {
            temp[i] = data[i];
        }

        data = temp;
    }

    /**
     * 索引越界的检查
     * 用于判断元素位置是否越界
     *
     * @param index
     * @return
     */
    private boolean isElementIndex(int index) {
        return index >= 0 && index < elementSize;
    }

    /**
     * 索引越界的检查
     * 用于判断插入元素的位置是否越界
     * 注意如果是增加元素, 有可能在最后一个元素后面
     *
     * @param index
     * @return
     */
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= elementSize;
    }

    /**
     * 检查 index 索引位置是否可以存在元素
     *
     * @param index
     */
    public void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", elementSize: " + elementSize);
        }
    }

    /**
     * 检查 index 索引位置是否可以添加元素
     *
     * @param index
     */
    public void checkPositionIndex(int index) {
        if (!isPositionIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", elementSize: " + elementSize);
        }
    }

    public void display() {
        System.out.println("elementSize = " + elementSize + ", cap = " + data.length);
        System.out.println(Arrays.toString(data));
    }
}
